package com.itheima.api.array.demo01;

/**
 * 数组的基本查找：
 *
 * 思路： 遍历数组，获取数组中的每一个元素，然后和要查找的元素进行比对，如果当前遍历的元素和要查找的元素值是相同的，那么我们就
 * 返回当前正在遍历的元素对应的索引，如果查找了一遍都没有进行返回，那么就说明，数组中不存在要查找的元素，那么我们就返回一个
 * 负数作为一个标识(-1)
 *
 */
public class ArrayDemo01 {

    // 入口
    public static void main(String[] args) {

        // 定义一个数组
        int[] arr = {23 , 45 , 89 , 100 , 11} ;
        
        // 调用方法进行元素的查找
        int index = baseSearch(arr, 150);
        System.out.println(index);

        System.out.println("----------------------------------------------------");

        // 定义数组
        int[] arr2 = {11 , 22 , 33 , 44 , 55 , 66 , 77 , 88 , 99 , 110 , 120} ;

        // 调用二分查找的方法
        int index2 = binarySearch(arr2 , 250);
        System.out.println(index2);

        System.out.println("-------------------------------------------");

        // 存在两个变量，a ， b
        int a = 23 ;
        int b = 45 ;

        // 把a和b的值进行交互
        int temp = a ;
        a = b ;
        b = temp ;

        System.out.println("a:" + a);
        System.out.println("b:" + b);

    }


    /** 进行二分查找
     * arr： 数组
     * key:  要查找的元素值
     * @param arr
     * @param key
     * @return
     */
    public static int binarySearch(int[] arr , int key) {

        // 定义变量
        int minIndex = 0 ;
        int maxIndex = arr.length - 1 ;

        // 计算中间索引
        int midIndex = (minIndex + maxIndex) / 2 ;

        while(minIndex <= maxIndex) {

            // 使用中间索引的值和要查找的元素进行比对
            if(arr[midIndex] == key) {
                return midIndex ;
            }else if(arr[midIndex] > key) {
                maxIndex = midIndex - 1 ;
            }else {
                minIndex = midIndex + 1 ;
            }

            // 重新计算中间索引
            midIndex = (minIndex + maxIndex) / 2 ;

        }

        // 返回-1
        return -1 ;

    }


    // 基本查找的方法

    /**
     * arr： 数组
     * key:  要查找的元素值
     * @param arr
     * @param key
     * @return
     */
    public static int baseSearch(int[] arr , int key) {

        for(int x = 0 ; x < arr.length ; x++) {
            if(arr[x] == key) {
                return x ;
            }
        }

        return -1;

    }



}
